package com.hy;

import java.util.Arrays;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:最大正方形
 * 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
 * author: Mr.Du
 * Date: 2023/5/7
 * Time: 17:31
 */
public class MaximalSquare {
    
    public static void main(String[] args) {
        char[][] matrix = new char[][]{
                {'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1', '1'},
                {'1', '1', '1', '1', '1'},
                {'1', '0', '0', '1', '0'},
                
        };
        int res = maximalSquare(matrix);
        System.out.println(res);
    }
    
    /**
     * 我们定义matrix(i,j) == 1时，就是一个单位的正方形
     * 状态定义：dp[i][j]表示以第i行第j列为正方形的右下角的单位边长
     * 只要matrix(i,j) == 0,那么以第i行第j列为正方形的右下角的单位边长就为0，不存在正方形
     * matrix(i,j) == 1,那么以第i行第j列为正方形的右下角的单位边长就要看跟它相邻的左、上、左上三个部分最小的，
     * 为啥是最小呢？
     * 看图理解去，淦！！！
     * @param matrix
     * @return
     */
    public static int maximalSquare(char[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m][n];
        int res = 0;
        for(int i = 0;i < m;i++){
            dp[i][0] = matrix[i][0] - '0';
            res = Math.max(res, dp[i][0]);
        }
        for(int i = 0;i < n;i++){
            dp[0][i] = matrix[0][i] - '0';
            res = Math.max(res, dp[0][i]);
        }
        for(int i = 1;i < m;i++){
            for(int j = 1;j < n;j++){
                if(matrix[i][j] - '0' == 0){
                    dp[i][j] = 0;
                }else{
                    dp[i][j] = Math.min(Math.min(dp[i-1][j-1],dp[i-1][j]), dp[i][j-1]) + 1;
                }
                res = Math.max(res, dp[i][j]);
            }
        }
        return res * res;
    }
    
    /**
     * 优化，将数组长度加1，就不用初始化dp数组啦!!!
     * @param matrix
     * @return
     */
    public static int maximalSquare1(char[][] matrix){
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m + 1][n + 1];
        int res = 0;
        for(int i = 1;i < m + 1;i++){
            for(int j = 1;j < n + 1;j++){
                if(matrix[i - 1][j - 1] - '0' == 1){
                    dp[i][j] = Math.min(
                            Math.min(dp[i-1][j-1],dp[i-1][j]),
                            dp[i][j-1]) + 1;
                }
                res = Math.max(res, dp[i][j]);
            }
        }
        return res * res;
    }
}
